package com.guo.skip.list;

import java.util.Arrays;

/**
 * @author gonghuaiguo
 * 跳表的简单实现
 */
public class SkipList {

    /**
     * 跳表索引的最大高度16
     */
    public static final int MAX_LEVEL = 16;
    /**
     * 每个节点添加一层索引高度的概率为0.5
     */
    public static final float PROB = 0.5f;
    /**
     * 默认情况下 高度为1 及默认一个节点
     */
    private int levelCount = 1;
    /**
     * 头结点
     */
    public Node head = new Node();


    public class Node {
        private int data = -1;
        private int maxLevel = 0;
        private Node[] forwards = new Node[MAX_LEVEL];

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", maxLevel=" + maxLevel +
                    ", forwards=" + Arrays.toString(forwards) +
                    '}';
        }
    }

    /**
     * 理论来说：
     * 一级索引的概率为50%，二级索引的概率为25%，三级索引的概率为12.5%
     * 每插入一个节点都需要判断，生成一个合理的层数
     *
     * @return
     */
    private int randomLevel() {
        int level = 1;
        while (Math.random() > PROB && level < MAX_LEVEL) {
            ++level;
        }
        return level;
    }

    /**
     * 新增
     *
     * @param value
     */
    public void add(int value) {

        // 随机生成高度
        int level = randomLevel();

        Node newNode = new Node();
        newNode.data = value;
        newNode.maxLevel = level;

        //创建一个node数组，用于记录小鱼当前value的最大值
        Node[] maxOfMinArr = new Node[level];
        //默认情况下指向头节点
        for (int i = 0; i < level; i++) {
            maxOfMinArr[i] = head;
        }

        // 基于上述结果拿到当前节点的后继节点
        Node p = head;
        for (int i = level-1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            maxOfMinArr[i] = p;
        }

        // 更新前驱节点的后继节点为当前节点newNode
        for (int i = 0; i < level; i++) {
            newNode.forwards[i] = maxOfMinArr[i].forwards[i];
            maxOfMinArr[i].forwards[i] = newNode;
        }

        // 如果当前newNode高度大于跳表最高高度则更新levelCount
        if (levelCount < level) {
            levelCount = level;
        }
    }

    /**
     * 获取值
     *
     * @param value
     * @return
     */
    public Node get(int value) {
        Node p = head;
        // 找到小于value的最大值
        for (int i = levelCount-1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
        }

        // 如果p的前驱节点等于value则直接返回
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            return p.forwards[0];
        }

        return null;
    }

    /**
     * 删除
     *
     * @param value
     */
    public void delete(int value) {
        Node p = head;
        //找到各级节点小于value的最大值
        Node[] updateArr = new Node[levelCount];
        for (int i = levelCount-1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            updateArr[i] = p;
        }

        // 查看原始节点前驱是否等于value 若等于则说明存在要删除的值
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            // 从最高级索引开始查看其前驱是否等于value，若等于则将当前节点指向value节点的后续解答
            for (int i = levelCount-1; i >= 0; i--) {
                if (updateArr[i].forwards[i] != null && updateArr[i].forwards[i].data == value) {
                    updateArr[i].forwards[i] = updateArr[i].forwards[i].forwards[i];
                }
            }
        }

        // 从最高级开始查看是否有一级索引为空，若为空则层级减1
        while (levelCount > 1 && head.forwards[levelCount - 1] == null) {
            levelCount--;
        }
    }

    public void printAll() {
        Node p = head;
        // 基于最底层的非索引层进行遍历，只要后继节点不为空，则速速出当前节点，并移动到后继节点
        while (p.forwards[0] != null){
            System.out.println(p.forwards[0]);
            p = p.forwards[0];
        }
    }

    public static void main(String[] args) {
        SkipList skipList = new SkipList();
        for (int i = 0; i < 24; i++) {
            skipList.add(i);
        }
        System.out.println("**********输出添加结果***********");
        skipList.printAll();

        SkipList.Node node = skipList.get(22);
        System.out.println("**********查询结果:" + node + "***********");
        skipList.delete(22);
        System.out.println("*************删除结果**************");
        skipList.printAll();


    }
}
